Теорема Эйлера о плоских графах

Если обыкновенный связный плоский граф имеет $n$ вершин, $m$ ребер и $r$ граней, то $n - m + r = 2$.

Пусть обыкновенный связный плоский граф $G$ имеет $n$ вершин, $m$ ребер и $r$ граней. Если в $G$ нет циклов, то $G$ является деревом. В этом случае в $G$ нет граней, отличных от внешней, следовательно $r=1$. По свойству деревьев, для него выполняется $n = m + 1$. Тогда $n - m + r = (m+1) - m + 1 = 2$. Пусть $G$ содержит циклы, и ребро $e$ принадлежит циклу. Положим $G_1 = G-e$. Граф $G_1$ является плоским и остается связным, так как ребро $e$ не является мостом в $G$. По лемме о числе границ, ребро $e$ принадлежит границе ровно двух граней графа $G$. При удалении $e$ эти грани сливаются в одну, а остальные грани не изменяются. Пусть $n_1, m_1, r_1$ — параметры графа $G_1$. Тогда $n_1 = n$, $m_1 = m-1$, $r_1 = r-1$. Следовательно, $n_1 - m_1 + r_1 = n - (m-1) + (r-1) = n - m + r$. Будем повторять процедуру удаления ребра, принадлежащего циклу, до тех пор, пока очередной граф $G_i$ с параметрами $n_i, m_i, r_i$ не станет деревом. Используя доказанное выше равенство для деревьев, получим: $$n - m + r = n_1 - m_1 + r_1 = \dots = n_i - m_i + r_i = 2$$ $\square$

Все изображения планарного графа имеют одинаковое число граней.

В планарном $(n,m,r)$-графе с $c$ компонентами связности, то $n - m + r = c + 1$.